前言

大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
那就開始今天的解題吧~

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9.
• Only one valid answer exists.

Follow up: Can you come up with an algorithm that is less than O(n2) time complexity?

Think

從陣列中找出兩個值加總為target，並回傳兩個值的index。

用一個count_dict來存每個數字出現的字數，最後找出dictionary中values()最大值的index，再透過index找出對應的key值，重複這個步驟k次。

Code

• 暴力解

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        remain = 0
        
        for num1 in range(len(nums)-1):
            remain = target - nums[num1]
            for num2 in range(num1+1, len(nums)):
                if remain == nums[num2]:
                    return [num1,num2]
 

• 另解

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        remain = 0
                
        num_dict = {}
        for index, num in enumerate(nums):
            remain = target - num
            if remain in num_dict:
                return [num_dict[remain], index]
            num_dict[num] = index
        
        

Submission

• 暴力解
  

• 另解
  

今天就到這邊啦~
大家明天見